class Solution {//LCR159——库存管理
private:
    void q_search(vector<int>& nums,int begin,int end,int cnt){
        if(begin>=end) return;
        int key=RandomKey(nums,begin,end);
        int left=begin-1,right=end+1,i=begin;
        while(i<right){
            if(nums[i]<key) swap(nums[i++],nums[++left]);
            else if(nums[i]==key) i++;
            else swap(nums[--right],nums[i]);
        }
        int a=left-begin+1,b=right-left-1,c=end-right+1;
        if(a>=cnt) q_search(nums,begin,left,cnt);
        else if(a+b>=cnt) return;
        else q_search(nums,right,end,cnt-a-b);
    }
    int RandomKey(vector<int>&nums,int begin,int end){
        return  nums[rand()%(end-begin+1)+begin];
    }
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(nullptr));
        q_search(stock,0,stock.size()-1,cnt);
        vector<int>ret(cnt); 
        for(int i=0;i<cnt;i++){
            ret[i]=stock[i];
        }
        return ret;
    }
};